package edu.dhu.leetcode2.bfsAnddfs;

import java.util.List;

/**
 * @Author ：snow
 * @Date ：Created in 2020-10-16
 * @Description：
 * @Modified By：
 * @Version:
 */
public class LadderLength127 {
    private int min_change = Integer.MAX_VALUE;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        dfs(beginWord, endWord,wordList, 0);
        return min_change == Integer.MAX_VALUE ? 0 : min_change;
    }
    private void dfs(String start, String end, List<String> list, int change){
        if (start.equals(end)){
            min_change = change;
        }
        for (int i = 0; i < list.size(); i ++){
            String piece = list.get(i);
            int diff = 0;
            for (int j = 0; j < start.length(); j++){
                if (start.charAt(j) != piece.charAt(j)) diff ++;
            }

            if (diff == 1){
                list.set(i, null);
                dfs(piece, end, list, change + 1);
                list.set(i, piece);
            }
        }
    }
}
